package com.ai.zuochengyun.phase01.class06;

import com.ai.zuochengyun.phase01.class05.Code01_UnionFind;

import java.util.*;

/**
 * 最小生成树
 * K算法  将边按权重的升序排序，然后依次取出之后
 * 通过并查集的方式，将不同的集合的节点合并起来
 */
public class Code06_Kruskal {
    public static Set<Edge> kruskalMST(Graph graph) {
        List<Node> values = new ArrayList<>(graph.nodes.values());
        Code01_UnionFind.UnionSet uf = new Code01_UnionFind.UnionSet(values);

        // 新建一个优先级队列
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new MyComparator());
        priorityQueue.addAll(graph.edges);

        // 依次弹出最小的值
        Set<Edge> res = new HashSet<>();
        while (!priorityQueue.isEmpty()) {
            // 当前边两端的节点是否是同一个集合
            Edge edge = priorityQueue.poll();
            boolean sameSet = uf.isSameSet(edge.from, edge.to);
            if (!sameSet) {
                res.add(edge);
                uf.union(edge.from, edge.to);
            }
        }
        return res;
    }


    /**
     * 倒序排序  深度越深的拓扑序越靠前
     */
    private static class MyComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            // 返回负数，第一个参数排前面，返回正数，第二个参数排前面
            return o1.weight - o2.weight;
        }
    }
}
